package zuo.middleLevel_7;

/**
 * @Author: Forx
 * @Data: 2021/6/26
 * @Desc: Algorithm - zuo.middleLevel_7
 * @Version: v1.0
 */
public class ML7 {
    /**
     *  X..X...XXX..X
     *  有上面的数组,X的地方不用管
     *  .的地方是需要点亮的,也可以放灯
     *  一个灯可以照亮相邻两边
     *  输出最少的路灯个数
     *
     * */

    public static class LIGHT{
        private String testString;

        public LIGHT(String testString) {
            this.testString = testString;
        }

        public void setTestString(String testString) {
            this.testString = testString;
        }
        public static int getMinLights(String string){
            if(string==null || string.isEmpty())return 0;
            string = string.toUpperCase();
            char[] chars = string.toCharArray();
            return process(chars,0);
        }
        public static int process(char[] chars,int left){
            if(left>chars.length-1)return 0;
            if(left==chars.length-1){
                if(chars[chars.length-1]=='X'){
                    return 0;
                }else {
                    return 1;
                }
            }
            if(left == chars.length-2){
                if(chars[left]=='.' || chars[left+1]=='.'){
                    return 1;
                }else {
                    return 0;
                }
            }
            if(left==chars.length-3){
                if(chars[left+1]=='.'){
                    return 1;
                }else {
                    if(chars[left]=='.'&&chars[left+2]=='.'){
                        return 2;
                    }else if(chars[left]=='.' || chars[left+2]=='.'){
                        return 1;
                    }else{
                        return 0;
                    }
                }
            }

            int index = left;
            int num = 0;
            while (chars[index]=='X'){
                index++;
            }
            if(chars[index+1]=='.'){
                num = process(chars,index+3)+1;
            }else {
                num = process(chars,index+2)+1;
            }
            return num;
        }
    }
    /**
     * 给定一棵树的先序和中序数组,返回后序数组
     * */
    public static class PRE_IN2POST{
        private static int[] pre_in2Post(int[] preOrder,int[] inOrder){
            if(preOrder.length!=inOrder.length)return null;
            int[] inIndex = new int[preOrder.length];
            for (int i = 0; i < preOrder.length; i++) {
                for (int j = 0; j < preOrder.length; j++) {
                    if(inOrder[j] == preOrder[i]){
                        inIndex[i] = j;
                        break;
                    }
                }
            }
            int[] out = new int[preOrder.length];
            process(preOrder,inOrder,inIndex,out,0,preOrder.length-1,0,inOrder.length-1);
            return out;
        }
        private static void process(int[] preOrder,int[] inOrder,int[] inIndex,int[] out,int preStart,int preEnd,int inStart,int inEnd){
            if(inEnd==inStart){
                System.out.println(inOrder[inStart] );
                return;
            }
            int leftLen = inIndex[preStart] - inStart;
            int rightLen =inEnd - inIndex[preStart];
            process(preOrder,inOrder,inIndex,out,preStart+1,preStart+leftLen,inStart,inStart+leftLen-1);
            process(preOrder,inOrder,inIndex,out,preStart+leftLen+1,preEnd,inStart+leftLen+1,inStart+leftLen+1+rightLen-1);
            System.out.println(preOrder[preStart] );
        }
        private static void verifySolution(){
            int[] pre = {1,2,4,5,3,6,7};
            int[] in = {4,2,5,1,6,3,7};
            pre_in2Post(pre,in);
        }
    }
    /**
     * 给定一个数组长度为N,且其中元素均位于区间[1,N]内,
     * 元素会重复,请找出未出现的元素,时间复杂度为O(n),
     * 空间复杂度为O(1),返回数组的空间不计入;
     * input:[1 3 4 3] output:[2]
     * */
    public static class FINDUNREPEAT{
        public static void findNoInArray(int[] arr){
            if(arr==null || arr.length==0){
                return;
            }
            for (int val : arr){
                modify(val,arr);
            }
            for (int i = 0; i < arr.length; i++) {
                if(arr[i]!=i+1){
                    System.out.println(i+1);
                }
            }
        }

        public static void modify(int val , int[] arr){
            while (arr[val-1]!=val){
                int temp = arr[val-1];
                arr[val-1] = val;
                val = temp;
            }
        }
    }
    /**
     * 不遍历求完全二叉树的节点个数
     *
     * 我的思路:从左边开始遍历,直到遇到一个节点的右子树为空停止遍历
     * 然后靠之前遍历左子树时获得的深度和叶子节点个数算得总节点数
     * */
    public static class COMPLETEBTSIZE{
        public static class Node{
            public Node left;
            public Node right;
            public int val;

            public Node(int val) {
                this.val = val;
                left = null;
                right = null;
            }
        }

        public static int nodeNum(Node head){
            if(head==null){
                return 0;
            }
            return nodeNumProcess(head,1,getMostLeftHeight(head,1));
        }
        private static int nodeNumProcess(Node node,int level,int h){
            if(level==h){
                return 1;
            }
            if(getMostLeftHeight(node.right,level+1)==h){
                //(1<<(h-level))是左子树的size
                return (1<<(h-level) + nodeNumProcess(node.right,level+1,h));
            }else {
                //(1<<(h-level-1))是右子树的size
                return (1<<(h-level-1) + nodeNumProcess(node.left,level+1,h));
            }
        }
        private static int getMostLeftHeight(Node node, int level){
            while (node!=null){
                level++;
                node = node.left;
            }
            return level-1;
        }
    }
    /**
     * 最长子序列问题,序列可以不连续的
     * 如3 1 2 6 3' 4
     * 最长子序列 1 2 3' 4
     *
     * 未完成
     * */
    public static class MAXSUBSERI{
        public static int findMinSub(int[] arr) {
            int[] dp = new int[arr.length];
            int[] ends = new int[arr.length];
            int endIndex = 0;
            int arrIndex = 0;
            ends[endIndex] = arr[arrIndex];
            while (endIndex < arr.length) {
                int leftIndex = findMinleft(arr[arrIndex],ends,endIndex);
            }
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++) {
                if(dp[i]>max){
                    max = dp[i];
                }
            }
            return max;
        }
        public static int findMinleft(int val,int[]ends,int endsEnd){
            int left = 0;
            int right = endsEnd;
            int mid = left + (right-left)>>1;
            //
            for (int i = 0; i < endsEnd; i++) {
                if(ends[i]<val&&ends[i+1]>=val){
                    return i+1;
                }
            }
            return endsEnd;
        }
    }



    public static void main(String[] args) {
        //System.out.println(LIGHT.getMinLights("XX.XX...X......X."));
        PRE_IN2POST.verifySolution();
    }
}
